#pragma once
namespace graph
{
   namespace algorithm
   {     
      //you need this data structures to get data from astar algorithm
      //alg_data_container_t - data for vertices, which visited by astar algorithm, indexed by vert id
      template<typename value_type>
      struct alg_data_container_t
      {
         //typedef std::map< vertex_id_t, value_type > data_t;
         typedef boost::unordered_map<vertex_id_t, value_type > data_t;
         alg_data_container_t(vertex_id_t vertex_count)
         {}
         alg_data_container_t()
         {}

         bool has_key(vertex_id_t v_id) const;
         value_type& get_value(vertex_id_t v_id);
         value_type const & get_value(vertex_id_t v_id) const;
         void set_value(vertex_id_t v_id, value_type val);
         value_type& operator[](vertex_id_t v_id);
         value_type const & operator[](vertex_id_t v_id) const;
         typename data_t::iterator begin();
         typename data_t::iterator end();
      private:
         data_t data_;
      };
      static vertex_id_t const START_VERTEX_ID = -1;
      static vertex_id_t const FINISH_VERTEX_ID = -2;
      
      struct min_heap_t
      {         
         min_heap_t()
           :   heap_size_(0)
         {}   
         typedef std::pair<lat_lon_t, vertex_id_t> heap_element_t;      
         typedef std::vector<heap_element_t> container_t;
         
         void insert(lat_lon_t key, vertex_id_t id);
         container_t::const_iterator begin();
         container_t::const_iterator end();
         vertex_id_t minimum() const;
         vertex_id_t extract_min();
         void dec_key_by_id(lat_lon_t key, vertex_id_t id);
         bool empty() const;
         bool has_key(vertex_id_t id) const;
         size_t size() const;
      private:
         typedef std::pair<vertex_id_t, size_t> id_pos_map_elem_t;
         //don't use element at 0
         //computation of children needs  beginiing at 1
         container_t heap_;
         boost::unordered_map<vertex_id_t, size_t> vertex_id_position_map_;
         size_t heap_size_;
         static size_t parent(size_t idx);
         static size_t left(size_t idx);
         static size_t right(size_t idx);
         
         void min_heapify(size_t idx);
         void build_min_heap();
         void dec_key_by_idx(lat_lon_t key, size_t idx);         
      };
   }
}
